# -*- coding: utf-8 -*-

class Node():
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


class SingleLinkedList():
    """1. 查询第几个元素
    2. 查询某个元素
    
    3. 添加一个元素
    4. 插入一个元素
    
    5. 删除尾部元素
    6. 删除一个元素
    7. 删除某个元素
    
    8. 切片
    9. 扩展
    10. 反转
    11. 遍历
    """
    def __init__(self, *datas):
        self.head = Node(None)
        self.length = 0
        
        if datas:
            for data in datas:
                self.append(data)
    
    def find(self, i):
        """根据序号查询元素"""
        if i >= self.length:
            raise IndexError()

        x, p = 0, self.head.next
        while True:            
            if x == i:
                break
            p = p.next
            x += 1

        return p.data

    def find_item(self, data):
        """根据元素查询序号
        查无此元素的情况下，最终 p==None，抛出 AttributeError"""
        try:
            i, p = 0, self.head.next
            while True:
                if p.data == data:
                    break
                p = p.next
                i += 1

            return i
        except AttributeError:
            raise KeyError()
    
    def append(self, data):
        p = self.head
        while True:
            if not p.next:
                break
            p = p.next

        p.next = Node(data)
        self.length += 1

    def insert(self, i, data):
        """i介于[0, length)之间"""
        if i >= self.length or i < 0:
            if self.length:
                raise KeyError()

        x, pre, p = 0, self.head, self.head.next
        while True:
            if x == i:
                break
            x, pre, p = x+1, pre.next, p.next

        pre.next = Node(data, p)
        self.length += 1
    
    def pop(self):
        if not self.head.next:
            raise IndexError()

        pre, p = self.head, self.head.next
        while True:
            if not p.next:
                break
            pre, p = pre.next, p.next
        
        pre.next = None
        self.length -= 1
        return p.data
    
    def remove(self, i):
        if i < 0 or i >= self.length:
            raise KeyError()

        x, pre, p = 0, self.head, self.head.next
        while True:
            if x == i:
                break
            x, pre, p = x+1, pre.next, p.next

        pre.next = p.next
        self.length -= 1

    def remove_item(self, data):
        pre, p = self.head, self.head.next
        while True:
            if p.data == data:
                break
            pre, p = pre.next, p.next
        
        pre.next = p.next
        self.length -= 1

    def slice(self, i, j):
        """切片后返回新的链表，不影响原链表"""
        if i<0 or i>j or j>=self.length:
            raise IndexError()
        
        new_list = SingleLinkedList()

        x, p = 0, self.head.next
        while True:
            if x > j:
                break
            
            if x >= i:
                new_list.append(p.data)

            x, p =  x+1, p.next
        
        return new_list

    def extend(self, other_linked_list):
        """直接修改原链表"""
        p = self.head
        while True:
            if not p.next:
                break
            p = p.next

        p.next = other_linked_list.head.next
        self.length += other_linked_list.length

    def reverse(self):
        """链表原位反转"""
        p = self.head.next
        if not p:
            return
        
        self.head.next = None
        while True:
            if not p.next:
                break

            temp = p
            p = p.next
            temp.next = self.head.next
            self.head.next = temp
        
        p.next = self.head.next
        self.head.next = p            

    def __iter__(self):
        p = self.head.next
        while True:
            if not p.next:
                break
            yield p.data
            p = p.next
        yield p.data


class CircularLinkedList():
    pass


class DoubleLinkedList():
    pass

if __name__ == '__main__':
    sl = SingleLinkedList(0,1,2,3,4,5)
    sl.append('a')
    sl.insert(2, 'b')

    for i in sl:
        print(i, end=', ')
    
    print('\n', sl.find(3))
    print(sl.find_item('a'))
    sl.pop()
    sl.remove(3)
    sl.remove_item('b')

    sl.extend(SingleLinkedList('q','q','q','q','q'))

    for i in sl:
        print(i)

    newsl = sl.slice(3, 8)

    for i in newsl:
        print(i, end=', ')

    # sl.reverse()

    # for i in sl:
    #     print(i)


